package question.solution220;

import question.SolutionTemplate;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class Solution220 implements SolutionTemplate {

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        Map<Long, Long> bucketMap = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            long id = getId(nums[i], t);
            if(bucketMap.containsKey(id)){
                return true;
            }
            if(bucketMap.containsKey(id-1) && Math.abs(bucketMap.get(id-1) - nums[i]) <= t){
                return true;
            }
            if(bucketMap.containsKey(id+1) && Math.abs(bucketMap.get(id+1) - nums[i]) <= t){
                return true;
            }
            bucketMap.put(id, (long)nums[i]);
            if(i >=k){
                bucketMap.remove(getId(nums[i-k],t));
            }
        }
        return false;
    }

    private long getId(int num, int t){
        long numL = num;
        if(num < 0){
            return (numL-t)/ (t+1);
        }
        return num / (t+1);
    }

    public void test() {
        int[] nums = {-2147483648,2147483647};
        int k=1;
        int t=1;
        boolean result = containsNearbyAlmostDuplicate(nums, k, t);
        long ll = Long.MAX_VALUE;

        long i=ll/2;
        return;
    }
}
